/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * 旋转方式打印矩阵
 * 递归/非递归方式
 * [
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
    ]
You should return [1,2,3,6,9,8,7,4,5]. 
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月17日
 */
public class SpiralMatrix {
    /**
     * 矩阵元素由外到里的旋转
     * @param matrix
     * @return
     * @author towan
     * 2015年5月17日
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        //初始条件判断
        if(matrix==null || matrix.length<=0 || matrix[0].length<=0){
            return result;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        //遍历位置
        int start = 0;
        while(col>start*2 && row>start*2){//循环条件【】
            addMatInCircle(matrix,start,result);
            start++;
        }
        return result;
    }

    /**
     * 将遍历的结果加入到结果列表中，一圈的遍历 左到右，右到下，下到左，左到上
     * @param matrix
     * @param start 遍历位置
     * @param result
     * @author towan
     * 2015年5月17日
     */
    private void addMatInCircle(int[][] matrix, int start, List<Integer> result) {
        int row = matrix.length;
        int col = matrix[0].length;
        
        int endX = col-1-start;
        int endY = row -1 -start;
        
        //左到右
        for(int i=start;i<=endX;i++){
            result.add(matrix[start][i]);
        }
        //右到下
        if(start<endY){
            for(int i=start+1;i<=endY;i++){
                result.add(matrix[i][endX]);
            }
        }
        //右到左
        if(start<endX && start<endY){
            for(int i=endX-1;i>=start;i--){
                result.add(matrix[endY][i]);
            }
        }
        //左到上
        if(start<endX && start<endY-1){
            for(int i=endY-1;i>=start+1;i--){
                result.add(matrix[i][start]);
            }
        }
    }
    public static void main(String[] args) {
        int [][]arr = {{1,2,3},{4,5,6},{7,8,9}};
        SpiralMatrix spiralMatrix = new SpiralMatrix();
        System.out.println(spiralMatrix.spiralOrder(arr));
        int [][]arr2 = null;
        System.out.println(spiralMatrix.spiralOrder(arr2));
        int [][]arr3 = {};
        System.out.println(spiralMatrix.spiralOrder(arr3));
    }
}
